from khronos.utils import INF, Namespace, Deque, Logger, Clock
from random import Random
from time import time
from sys import stdout

class BranchAndBound(object):
    """This class implements a general and fully configurable branch&bound algorithm, which must 
    be sub-classed for particular problems. Subclasses should define the following methods 
    (methods marked with * are advisable but not mandatory, and methods marked with ** are 
    completely optional):
        
        root()              # create the search's starting point (the tree's root node)
        copy(node)          # create an exact (deep) copy of a given node
        branches(node)      # list of branching options available at a node
        apply(node, branch) # modify a node by following a given branch
        objective(node)     # compute the objective function value of a given node
        
        *lower_bound(node) # compute a lower bound of the objective function for a given node
        *is_leaf(node)     # check whether a node is a leaf or not
        *rank(node)        # compute the rank of a node, which defines its position in the queue
        
        **dive_descent(node) # select the descent path of a dive, and optionally also select a 
                             # number of branches to be expanded into the queue of open nodes
        **select_explore()             # select the next queued node to explore
        **select_discard()             # select the next queued node to discard
        **collect_improvement(node, z) # collect information from improving nodes
        **collect_leaf(node, z)        # collect information from reached leaves
        **collect_pruned(node, lb)     # collect information from pruned nodes
        
    Please refer to the documentation on these methods for more information on their role in the 
    algorithm, and what they should implement.
    
    NOTES:
        - queue with possible size limitation
        - queue is sorted in ascending order
        - when fetching, by default, the highest-rank node at the queue is removed (pop())
    """
    indline_fmt = "%40s = %s"
    default_queue_size = INF
    default_diving = False
    
    def __init__(self, queue_size=None, diving=None, log=None, **kwargs):
        self.config = Namespace(queue_size=self.default_queue_size, 
                                diving=self.default_diving)
        self.state = Namespace(stop=None, 
                               cpu=Clock(),
                               count=Namespace(iterations=0,   # mainloop iterations (expand/dive)
                                               improvements=0, # improving solutions found
                                               leaves=0,       # leaves reached
                                               pruned=0,       # pruned nodes
                                               discarded=0,    # discarded nodes
                                               expanded=0,     # expanded nodes
                                               queued=0,       # queued nodes
                                               dives=0,        # successful dives
                                               aborted=0))     # aborted dives
        self.search = Namespace(instance=None,
                                solutions=[],
                                upper_bound=INF,
                                optimal=-INF,
                                queue=Deque(), 
                                rng=Random(),
                                metadata=Namespace())
        self.max = Namespace(cpu=INF, iterations=INF, improvements=INF)
        self.log = Logger(streams=xrange(5), show_name=False)
        self.configure(queue_size, diving, log)
        self.__dict__.update(kwargs)
        
    def configure(self, queue_size=None, diving=None, log=None):
        if queue_size is not None: self.config.queue_size = queue_size
        if diving     is not None: self.config.diving = diving
        if log        is not None: self.log.enabled = log
        
    def solve(self, instance=None, cpu=INF, iterations=INF, improvements=INF,
              upper_bound=INF, optimal=-INF, seed=None, **metadata):
        """Initialize the solver and start the search by calling run() if the search was
        not stopped after calling start(). If after start() the 'stop' state flag is not None, 
        it means that some stoppage criteria was met, so run() is not called."""
        self.start(instance, cpu, iterations, improvements, upper_bound, optimal, seed, **metadata)
        if self.state.stop is None:
            self.run(cpu - self.state.cpu.total, 
                     iterations - self.state.count.iterations, 
                     improvements - self.state.count.improvements)
        return self.best_solution()
        
    def start(self, instance=None, cpu=INF, iterations=INF, improvements=INF, 
              upper_bound=INF, optimal=-INF, seed=None, **metadata):
        """Solver initialization routine. Initializes all solver attributes and calls the 
        bootstrap() method to setup the search's starting point before the main loop."""
        if instance is None: instance = self.search.instance
        if seed     is None: seed = int(time() * 1000)
        # +++
        self.max.cpu = cpu
        self.max.iterations = iterations
        self.max.improvements = improvements
        
        self.state.stop = None
        self.state.cpu.clear()
        self.state.count = Namespace((x, 0) for x in self.state.count.iterkeys())
        
        self.search.instance = instance
        self.search.solutions = []
        self.search.upper_bound = upper_bound
        self.search.optimal = optimal
        self.search.queue.clear()
        self.search.rng.seed(seed)
        self.search.metadata = Namespace(metadata,
                                         max_queue_size=self.config.queue_size, 
                                         diving=self.config.diving,
                                         instance=self.search.instance,
                                         seed=seed)
        # +++
        self.log(" --- %s initialization --- " % (self.__class__.__name__,), width=100)
        for key, value in sorted(self.search.metadata.iteritems()):
            self.log(self.indline_fmt % (key, value))
        # +++
        with self.state.cpu.tracking():
            self.bootstrap()
        return self.best_solution()
        
    def bootstrap(self):
        """Create the root node and queue it before the main loop starts."""
        root = self.root()
        self.search.optimal = max(self.search.optimal, self.lower_bound(root))
        self.queue_node(root)
        
    def run(self, cpu=INF, iterations=INF, improvements=INF):
        """The body of the search. It starts by getting a node from the queue, and running a 
        loop where the node is explored (expand/dive), and a next node is fetched from the queue. 
        The loop stops when the queue is empty, or some stoppage criteria has been met (e.g. cpu 
        limit).
        
        IMPORTANT NOTE: An empty queue does not imply that the search tree has been exhausted 
        because some nodes may have been discarded during the search (due to limitation on the 
        size of the queue). However, if no nodes are discarded the search only stops when the 
        whole search tree has been explored. Note that this only implies global optimality if 
        the branching function does not exclude any branch from the search."""
        # Update all stoppage conditions.
        self.max.cpu = self.state.cpu.total + cpu
        self.max.iterations = self.state.count.iterations + iterations
        self.max.improvements = self.state.count.improvements + improvements
        # The main search loop from a very high level (tracked CPU time).
        explore = self.dive if self.config.diving else self.expand
        with self.state.cpu.tracking():
            try:
                self.state.stop = None
                current = self.advance()
                while self.state.stop is None:
                    explore(current.node)
                    self.state.count.iterations += 1
                    current = self.advance()
            except KeyboardInterrupt:
                self.state.stop = "search interrupted manually."
        if self.state.stop is not None:
            self.log.warn(self.state.stop)
        return self.best_solution()
        
    def step(self, iterations=1):
        """Shortcut method. Equivalent to run(iterations=xxx)."""
        self.run(iterations=iterations)
        
    def improve(self, improvements=1):
        """Shortcut method. Equivalent to run(improvements=xxx)."""
        self.run(improvements=improvements)
        
    def advance(self):
        """Get the next node to explore from the queue if no stoppage condition was met. The 
        index of the target node is given by the select_expore() method."""
        if len(self.search.queue) == 0:
            self.state.stop = "EMPTY QUEUE: discarded %d nodes." % (self.state.count.discarded,)
            return None
        if self.state.count.iterations >= self.max.iterations:
            self.state.stop = "ITERATION LIMIT: %d iterations." % (self.state.count.iterations,)
            return None
        if self.state.cpu.total >= self.max.cpu:
            self.state.stop = "CPU LIMIT: %s cpu seconds elapsed." % (self.state.cpu.total,)
            return None
        return self.search.queue.pop_at(self.select_explore())
        
    def expand(self, node, branches=None):
        """Expand a list of branches applied to a given node to create a list of child nodes. 
        These child nodes are then placed in the queue if possible, to be explored later.
        IMPORTANT NOTE: The argument node is modified by this method. If the node should be kept
        intact, then be sure to pass a copy of the node to this function, i.e. expand(copy(node)).
        """
        if branches is None:
            branches = self.branches(node)
        last_branch = branches.pop()
        for branch in branches:
            child = self.copy(node)
            self.apply(child, branch)
            self.queue_node(child)
        # Apply the last branch to the actual node only after all other children have been  
        # generated. This way we can use the node directly, avoiding one potentially expensive 
        # copy operation for each call to expand().
        self.apply(node, last_branch)
        self.queue_node(node)
        self.state.count.expanded += 1
        
    def dive(self, node, descent_fnc=None, abort=1.0):
        """Make a dive starting at the given node. The path of the dive and expansion of nodes 
        during the descent can be controlled by the descent_fnc() argument. This function should 
        return a tuple consisting of the dive path and branches that should be expanded into the 
        queue of open nodes.
        The dive can also be aborted whenever the node's LB becomes >= than the current UB 
        times the abort value. Note that if the abort value is infinity, the dive will not 
        abort because the lower bound should never be equal to positive infinity.
        The return value of a dive consists of a tuple containing the final node, the z-value 
        (or LB at the time of abortion), and a boolean flag telling whether the dive finished 
        (went to a leaf) or aborted (when LB >= abort * UB). Summarizing, if:
            1) somewhere during the dive the node's LB >= abort * UB, the dive is aborted and 
               the current node, its lower bound, and a finish flag equal to False are returned.
            2) a leaf node is reached, then the leaf, its objective function value, and a finish
               flag equal to True are returned.
        Format of the return tuple: (node, z_or_LB, finish_flag)
        IMPORTANT NOTE: The argument node is modified by this method. If the node should be kept
        intact, then be sure to pass a copy of the node to this function, i.e. dive(copy(node)).
        """
        if descent_fnc is None:
            descent_fnc = self.dive_descent
        abort_value = abort * self.search.upper_bound 
        while True:
            dive_path, to_expand = descent_fnc(node)
            if len(to_expand) > 0:
                self.expand(self.copy(node), to_expand)
            self.apply(node, dive_path)
            if self.is_leaf(node):
                objective = self.check_leaf(node)
                self.state.count.dives += 1
                return node, objective, True
            lower_bound = self.lower_bound(node)
            if lower_bound >= abort_value:
                self.state.count.aborted += 1
                return node, lower_bound, False
                
    def queue_node(self, node):
        """Attempt to add a node to the queue. If the node is a leaf node, or its lower bound is 
        greater or equal to the current upper bound, the node is pruned (not added to the queue 
        with certainty that it cannot lead to improving solutions). If none of the previous 
        conditions occurs, the node is ranked and added to the queue.
        If, after queuing the node, the queue is exceeding its maximum size, the discard_next() 
        method is used to select a node for discarding."""
        if self.is_leaf(node):
            self.check_leaf(node)
            return
        lower_bound = self.lower_bound(node)
        if lower_bound >= self.search.upper_bound:
            self.collect_pruned(node, lower_bound)
            self.state.count.pruned += 1
            return
        rank = (self.rank(node), self.search.rng.random())
        self.search.queue.insort(NodeWrapper(node, lower_bound, rank))
        self.state.count.queued += 1
        if len(self.search.queue) > self.config.queue_size:
            self.search.queue.pop_at(self.select_discard())
            self.state.count.discarded += 1
            
    def check_leaf(self, node):
        """Check a leaf node's objective function value. If it is less that the current upper 
        bound on the optimal objective function value, we build and add a solution to the 
        solution list, tighten the upper bound, and prune the queue with the new bound. The 
        search is stopped at this point if an optimal solution is found or the desired number 
        of improvements has been reached.
        NOTE: This method returns the objective function value of the given node."""
        z = self.objective(node)
        if z < self.search.upper_bound:
            self.log("IMPROVEMENT: %s -> %s" % (self.search.upper_bound, z), stream=4)
            self.add_solution(node, z)
            self.collect_improvement(node, z)
            self.state.count.improvements += 1
            self.search.upper_bound = z
            if z <= self.search.optimal:
                self.state.stop = "OPTIMAL SOLUTION: found optimal solution"
            else:
                if len(self.search.queue) > 0:
                    self.prune_queue()
                if self.state.count.improvements >= self.max.improvements:
                    self.state.stop = "IMPROVEMENT LIMIT REACHED: stopping search."
        else:
            self.collect_leaf(node, z)
        self.state.count.leaves += 1
        return z
        
    def prune_queue(self):
        """Queue pruning using an updated upper bound of the optimal objective function value 
        (z*). Nodes are removed from the queue if their lower bound is greater or equal to the 
        new upper bound, i.e. they cannot possibly lead to solutions better than the new upper 
        bound."""
        total = len(self.search.queue)
        pruned = 0
        kept = 0
        while kept < len(self.search.queue):
            wrapper = self.search.queue[0] 
            if wrapper.lower_bound >= self.search.upper_bound:
                self.search.queue.popleft()
                self.collect_pruned(wrapper.node, wrapper.lower_bound)
                pruned += 1
            else:
                self.search.queue.rotate(-1)
                kept += 1
        assert pruned + kept == total
        self.log("QUEUE PRUNING: Total %d, Kept %d, Pruned %d" % (total, kept, pruned))
        self.state.count.pruned += pruned
        
    def iter_queue(self):
        """Returns an iterator over the content of the node queue. This may be used by the 
        select_explore()/select_discard() methods, which return the index of the next node 
        to explore/discard, respectively. The return value of this method is a generator 
        yielding (index, node, LB, rank) tuples."""
        for index, wrapper in enumerate(self.search.queue):
            yield index, wrapper.node, wrapper.lower_bound, wrapper.rank
            
    def verify_queue(self):
        """Perform a sanity check to the contents of the queue. If any node is out of order 
        (rank-wise) or a node's LB is greater or equal to the current LB, an error message is 
        printed. This method returns the number of errors that were caught."""
        errors = 0
        if len(self.search.queue) > 0:
            prev_rank = self.search.queue[0].rank
            for index, wrapper in enumerate(self.search.queue):
                if wrapper.lower_bound >= self.search.upper_bound:
                    self.log.error("Non-improving node at position %d" % (index,))
                    errors += 1
                if wrapper.rank < prev_rank:
                    self.log.error("Rank inversion at position %d (%s > %s)" % 
                                   (index, prev_rank, node.rank))
                    errors += 1
                prev_rank = wrapper.rank
        return errors
        
    def add_solution(self, leaf, z):
        """Add an improving solution (leaf node) to the solution list. The solution is coupled 
        with a metadata dictionary containing a snapshot of the current status of the solver 
        (e.g. number of explored, discarded, pruned nodes, dives, z-value, cpu time, etc)."""
        meta = Namespace()
        meta.update(self.search.metadata)
        meta.update(self.state.count)
        meta.update(node=leaf, 
                    objective=z, 
                    queue_size=len(self.search.queue), 
                    search_speed=(self.state.count.iterations + 1) / self.state.cpu.total, 
                    cpu=self.state.cpu.total)
        self.search.solutions.append(meta)
        # Log the solution's metadata.
        self.log("=" * 100)
        for key, value in sorted(meta.iteritems()):
            self.log(self.indline_fmt % (key, value), width=100)
        self.log("=" * 100)
        
    def best_solution(self):
        """If at least one solution has been found, return the best of them. Note that the list 
        of solutions is ordered by decreasing z-value, so the last element of the list contains 
        our best solution. If the list is empty, None is returned.
        NOTE: a solution is a Namespace containing the solution itself as well as additional data 
        about the search state at the time the solution was obtained."""
        if len(self.search.solutions) > 0:
            return self.search.solutions[-1]
        return None
        
    # -----------------------------------------------------
    # Reporting and plotting ------------------------------
    def report(self, show_solutions=True, out=stdout):
        """Write a summary of the solver's configuration, current 
        search state and a summary of the solutions found so far."""
        fmt = self.indline_fmt + "\n"
        out.write(object.__repr__(self) + "\n")
        out.write(fmt % ("Explore method", "dive" if self.config.diving else "expand"))
        out.write(fmt % ("Maximum queue size", self.config.queue_size))
        if self.search.instance is not None:
            qsize = len(self.search.queue)
            qoccupation = 100.0 * qsize / self.config.queue_size
            gss = "%.3f iter/sec" % (self.state.count.iterations / self.state.cpu.total,)
            for key, value in [("Queue size", "%d (%.3f %%)" % (qsize, qoccupation)),
                               ("Total CPU time", self.state.cpu.total),
                               ("Global search speed (GSS)", gss),
                               ("Iterations",      self.state.count.iterations),
                               ("Queued nodes",    self.state.count.queued),
                               ("Pruned nodes",    self.state.count.pruned),
                               ("Discarded nodes", self.state.count.discarded),
                               ("Expanded nodes",  self.state.count.expanded),
                               ("Dives completed", self.state.count.dives),
                               ("Dives aborted",   self.state.count.aborted),
                               ("Leaves reached",  self.state.count.leaves),
                               ("Upper bound",     self.search.upper_bound),
                               ("Solutions found", len(self.search.solutions))]:
                out.write(fmt % (key, value))
            if show_solutions:
                prev_iter = 0
                prev_cpu = 0.0
                for x, sol in enumerate(self.search.solutions):
                    iss = (sol.iterations + 1 - prev_iter) / (sol.cpu - prev_cpu)
                    prev_iter = sol.iterations + 1
                    prev_cpu = sol.cpu
                    sol_info = "%s (obtained at %s, ISS=%.3f iter/sec)" % \
                        (sol.objective, sol.cpu, iss)
                    out.write(fmt % ("Solution %d" % (x,), sol_info))
                    
    def plot_solutions(self, filename=None, dpi=300):
        """Build and display or save a plot showing the evolution of the upper bound (aka the 
        best solution) over time. If filename is None, the plot is displayed to the screen, 
        otherwise it is saved to the specified file. The filename extension will determine the 
        format of the output file (e.g. pdf, eps, png, jpg)."""
        if len(self.search.solutions) == 0:
            self.log.error("No solutions to be plotted")
            return
        meta = self.search.solutions[0]
        cpu = meta.cpu
        objective = meta.objective
        xs = [cpu]
        ys = [objective]
        for meta in self.search.solutions[1:]:
            cpu = meta.cpu
            xs.append(cpu)
            ys.append(objective)
            objective = meta.objective
            xs.append(cpu)
            ys.append(objective)
        xs.append(self.state.cpu.total)
        ys.append(self.search.upper_bound)
        
        from matplotlib.pyplot import figure
        fig = figure()
        plot = fig.add_subplot(1, 1, 1)
        plot.set_title("Upper bound over time")
        plot.set_xlabel("CPU time (s)")
        plot.set_ylabel("Upper bound")
        plot.plot(xs, ys, color="blue", linewidth=2, 
                  marker="o", markeredgecolor="blue")
        if filename is None:
            fig.show()
        else:
            fig.savefig(filename, dpi=dpi)
            
    # -----------------------------------------------------
    # Queue inspection ------------------------------------
    def repr(self, node):
        return ""
        
    def show_nodes(self, x=0, n=INF):
        """Print the part of the queue starting at index 'x' and ending 
        at index 'x+n-1' (n is the number of elements printed)."""
        end = min(x + n, len(self.search.queue))
        while x < end:
            wrapper = self.search.queue[x]
            print "\t", x, "::", wrapper, self.repr(wrapper.node)
            x += 1
            
    def first_nodes(self, n=10):
        """Print the first n nodes on the queue."""
        n = min(n, len(self.search.queue))
        print "First %d nodes" % (n,)
        self.show_nodes(0, n)
        
    def last_nodes(self, n=10):
        """Print the last n nodes on the queue."""
        n = min(n, len(self.search.queue))
        print "Last %d nodes" % (n,)
        self.show_nodes(len(self.search.queue) - n, n)
        
    def edge_nodes(self, n=10):
        """Print the first and last n nodes on the queue."""
        self.first_nodes(n)
        self.last_nodes(n)
        
    # -----------------------------------------------------
    # Methods to redefine in subclasses -------------------
    def root(self): # MUST BE REDEFINED
        """Create and return the search's initial node."""
        raise NotImplementedError()
        
    def copy(self, node): # MUST BE REDEFINED
        """Create an exact copy of the given node. This method is extensively used because a lot
        of node copies are necessary while expanding a node's children. Extreme care should be 
        taken for shared information between nodes. If the shared data can somehow be modified 
        then each node should contain an independent copy of that data."""
        raise NotImplementedError()
        
    def branches(self, node): # MUST BE REDEFINED
        """Create a list of branches available at the given node. The elements of the branch list 
        should contain all the necessary information to apply a change to a node."""
        raise NotImplementedError()
        
    def apply(self, node, branch): # MUST BE REDEFINED
        """Apply a branch (an element of the branch list returned by branches()) to a node."""
        raise NotImplementedError()
        
    def objective(self, node): # MUST BE REDEFINED
        """Calculate and return the objective function value of a given leaf node."""
        raise NotImplementedError()
        
    def lower_bound(self, node): # SHOULD BE REDEFINED (TO ALLOW PRUNING)
        """Calculate and return a lower bound of the best objective function value (z) that can 
        be obtained through the given node. This method should absolutely not return a value 
        which is not a real lower bound of the z-value, as this may cause incorrect pruning 
        decisions. The default value (-INF) disables pruning, since every node will have a lower
        bound that is smaller than the upper bound of the z-value."""
        return -INF
        
    def is_leaf(self, node): # SHOULD BE REDEFINED (TO INCREASE SPEED IN LEAF CHECKING)
        """Return a boolean indicating whether the given node is a leaf or not. It is advisable
        to redefine this method in subclasses, but it's default behavior should work without 
        problem, although much slower than with an application-specific 'leafness' check. By 
        default, a node is considered a leaf if its list of available branches is empty."""
        return len(self.branches(node)) == 0
        
    def rank(self, node): # SHOULD BE REDEFINED (TO ALLOW QUEUE ORDERING)
        """Calculate and return the rank of a given node. The rank is used to define the order 
        by which nodes are placed in the queue (low to high rank). If the next node selection 
        method (select_explore()) selects the rightmost node every time, then the search becomes 
        best-first search, and rank guides the search order.
        By default, the CPU time elapsed so far is returned. This makes the search effectively 
        become depth-first, since CPU time is non-decreasing. A depth-first search should never, 
        in normal conditions, overcome the queue size limit unless it is inappropriately low."""
        return self.state.cpu.total
        
    def dive_descent(self, node): # COMPLETELY OPTIONAL
        """This method is used in dives to guide the direction of the descent as well as the 
        optional expansion of branches into the queue of open nodes during the dive. This method 
        should return a tuple containing the dive path and a list of branches to be expanded (can 
        be an empty list).
        The default behavior of this method is to obtain the list of all branches at the given 
        node using the branches() method, removing the last branch the from list, and using it as 
        the dive path. The remaining branches are returned as expansion branches. This is in fact 
        a full dive, which is prone to quickly fill the queue with open nodes."""
        branches = self.branches(node)
        dive_path = branches.pop()
        return dive_path, branches
        
    def select_explore(self): # COMPLETELY OPTIONAL
        """Return the index of the next node to explore from the queue. This method is used to 
        decide which point in the queue the next node is going to be taken from. The default 
        behavior is to simply return -1, making the next node always be at the right (high-rank) 
        end of the queue, which leads to best-first search.
        This method may be used to define dynamic ranking schemes, where the nodes in the queue 
        can be inspected and re-ranked every time a new node is to be explored. To iterate over 
        the queue contents, the iter_queue() method should be used."""
        return -1
        
    def select_discard(self): # COMPLETELY OPTIONAL
        """Return the index of the next node to discard from the queue. This method is used if 
        the maximum queue size was exceeded after an insertion. The default behavior is to simply 
        return 0, thus always discarding the node at the left (low-rank) end of the queue."""
        return 0
        
    def collect_improvement(self, node, z): # COMPLETELY OPTIONAL
        """Like collect_leaf(), but called only on improving nodes."""
        pass
        
    def collect_leaf(self, node, z): # COMPLETELY OPTIONAL
        """This method (and collect_pruned()) can be used to collect information for, e.g. guiding
        the search by updating the coefficients of an adaptive ranking function."""
        pass
        
    def collect_pruned(self, node, lb): # COMPLETELY OPTIONAL
        """This method (and collect_leaf()) can be used to collect information for, e.g. guiding
        the search by updating the coefficients of an adaptive ranking function."""
        pass
        
class NodeWrapper(object):
    """Node wrapper used to hold data necessary for the branch-and-bound tree nodes.
    This class implements rich comparison operators that compare based on the node's rank. 
    Comparison is used in this way to "insort()" nodes into the queue of open nodes.
    Attributes:
        node - The node's state information.
        lower_bound - A lower bound of the best z-value obtained through this node.
        rank - The node's rank (for positioning in the queue).
    """
    def __init__(self, node, lower_bound, rank):
        self.node = node
        self.lower_bound = lower_bound
        self.rank = rank
        
    def __repr__(self):
        return "<Node(R=%s, LB=%s) at 0x%08x>" % (self.rank, self.lower_bound, id(self))
        
    def __eq__(self, wrapper):
        return self.rank == wrapper.rank
        
    def __neq__(self, wrapper):
        return self.rank != wrapper.rank
        
    def __gt__(self, wrapper):
        return self.rank > wrapper.rank
        
    def __geq__(self, wrapper):
        return self.rank >= wrapper.rank
        
    def __lt__(self, wrapper):
        return self.rank < wrapper.rank
        
    def __leq__(self, wrapper):
        return self.rank <= wrapper.rank
        
